1. Field of the Invention
The present invention relates to a cache memory built in a microprocessor and, in particular, to a cache memory intended for simplification of its constitution and downsizing the hardware as well as for improvement of the hit ratio during loop processing.
2. Description of the Related Art
An example of a conventional cache memory built in a microprocessor, with a direct mapping system, for example, will be described below with reference to a block diagram of FIG. 1.
In the conventional cache memory shown in FIG. 1, an access address from the microprocessor has a 24-bit width, from bit 0 to bit 23, and the data is accessed in units of 32 bits.
In FIG. 1, reference numeral 1 represents an access address outputted from the microprocessor (not shown). The access address indicates a stored address in an external memory (not shown) of a data (instruction data or operand data) which is to be fetched by microprocessor.
By the way, the access address 1 has 24-bit width as mentioned above, of which the lower 8 bits are outputted to an address decoder 5 and the higher 16 bits are outputted to a comparator 6 respectively.
Reference numeral 2 represents an address information storing unit, capable of storing 256 units of the higher 16 bits of the access address 1 in this embodiment as described below.
Reference numeral 3 represents a data storing unit. The data storing unit 3 is a memory of 32-bit width capable of registering 256 pieces of data read/write accessed from the external memory (not shown) by a microprocessor in this embodiment as described below.
The address information storing unit 2 and the data storing unit 3 is composed of 256 entries in No. 1 to No. 256 determined uniquely by decoding the lower 8 bits of the access address 1. Accordingly, one entry of the cache memory shown in FIG. 1 is composed of a 16-bit region of the address information storing unit 2, a 32-bit region of the data storing unit 3 and 1 bit of valid bit storing unit 4 described below.
The valid bit storing unit 4 is composed of valid bits, each which corresponds to each entry of the address information storing unit 2 and data storing unit 3.
When each valid bit of the valid bit storing unit 4 is set to "1", it means that the data stored in an entry of the data storing unit 3 corresponding to the valid bit is valid, and when it is reset to "0", it means that the stored data is invalid.
Reference numeral 5 represents an address decoder. The address decoder 5, as aforementioned, specifies uniquely one entry of the 256 entries according to the decoding result of the lower 8 bits of the access address 1.
Reference numeral 6 represents a comparator, which compares the higher 16 bits of the access address 1 with the address information stored in the entry of the address information storing unit 2 specified by the address decoder 5. Then, when the valid bits of the valid bit storing unit 4 corresponding to the entry No. of the decoding result by the address decoder 5 is valid and comparison results agrees, the comparator 6 asserts a hit signal HIT.
As described below in detail, when the cache memory built in the microprocessor is hit (i.e. when the comparison result by the comparator 6 agrees and the data is valid) in read accessing by the microprocessor, the hit signal HIT from the comparator 6 is asserted and data is read from the corresponding entry of the data storing unit 3. When the comparison result of the comparator 6 do not agree, the value of the address information storing unit 2 is rewritten to the value of the higher 16 bits of the access address 1 newly accessed.
The reading operation of the conventional cache memory shown in FIG. 1 will be explained below.
When the system as a whole is reset, all valid bits of the valid bit storing unit 4 are reset.
From this state, the operation when the cache memory makes a read miss with regard to read access from the microprocessor is as described below.
When read access with regard to an address "000000h (h indicates hexadecimal notation)" is started, the cache memory operates as follows.
The address decoder 5 decodes the lower 8 bits "00h" in the access address 1. In this case, the No. 1 entry is obtained as a decoding result of "00h".
Then, the address stored in the No. 1 entry of the address information storing unit 2 is compared with the higher 16 bits of the access address 1 by the comparator 6 and simultaneously set/reset of the valid bit of No. 1 entry of the valid bit storing unit 4 is checked.
When the comparison result by the comparator 6 agrees and also the valid bit of the corresponding entry of the valid bit memory 4 is valid, it is judged as hit and the hit signal HIT is asserted. That is, data corresponding to the access address 1 is judged as already registered in the cache memory, specifically in the data storing unit 3.
However, since immediately after resetting of the system as a whole, valid bit of No. 1 entry of the valid bit storing unit 4 is reset, it is judged that the data is not registered (cache miss).
When such a cache miss has occurred, read access by the microprocessor is done to the external memory.
Now, for example, it is supposed that the microprocessor has read accessed the data "AAAAAAAAh" of the address "000000h". In this case, the value of the higher 16 bits "0000h" is stored in No. 1 entry of the address information storing unit 2 corresponding to the entry No. 1 obtained by decoding the lower 8 bits of the access address 1 by means of the address decoder 5, the data "AAAAAAAAh" taken into the microprocessor by the read access is stored in No. 1 entry of the data storing unit 3, and the valid bit of No. 1 entry of the valid bit storing unit 4 is set to "1".
Thus, the data "AAAAAAAAh" of the address "000000h" is registered in No. 1 entry of the cache memory.
FIG. 2 is a schematic diagram showing stored contents of the address information storing unit 2, data storing unit 3 and valid bit storing unit 4 after the microprocessor has accessed the address "000000h".
Thus, when the cache memory makes cache miss, the data read accessed from the external memory is registered in the cache memory.
Next, operation when the microprocessor has again accessed the data already registered in the cache memory will be explained.
When the microprocessor has again accessed to the address "00000h", the address "0000h" stored in No. 1 entry of the address information storing unit 2 is compared with the higher 16 bits of the access address 1 by the comparator 6. Simultaneously, set/reset of the valid bit of No. 1 entry of the valid bit storing unit 4 is checked. When the comparison result by the comparator 6 agrees and the valid bit is valid, it is judged that the data of the access address 1 is registered and the hit signal HIT is asserted.
Under the condition shown in FIG. 2, the address stored in No. 1 entry of the address information storing unit 2 agrees, being "0000h", and valid bit of No. 1 entry of the valid bit storing unit 4, too, is set to "1" (valid), hence it is judged that the access data is already registered in No. 1 entry of the cache memory. As a result, the data "AAAAAAAAh" stored in No. 1 entry of the data storing unit 3 is outputted to the microprocessor.
Operation when a read miss has occurred once again will be explained.
Now, taken as example is the case where the access address 1 from the microprocessor is "000001h" with its higher 16 bits same as but the lower 8 bits different, from above-mentioned access address "000000h".
When the address decoder 5 decodes the lower 8 bits "01h" of the access address 1, entry No. 2 is obtained. Since this entry No. 2 is different from the entry No. 1 resulting from decoding the aforementioned access address "000000h", the higher 16 bits "0000h" of the access address 1 are stored in No. 2 entry of the address information storing unit 2, and the data "BBBBBBBBh" of the address "000001h" are stored in No. 2 entry of the data storing unit 3.
FIG. 3 is a schematic diagram showing the stored contents of the address information storing unit 2, data storing unit 3 and valid bit storing unit 4 after registering the data "BBBBBBBBh" of the address "000001h" in No. 2 entry of the cache memory by accessing the address "000001h".
As seen from FIG. 3, in the No. 1 and No. 2 entries of the address information storing unit 2, the same address "0000" is stored. Especially, when continuous addresses have been accessed as in the case of instruction fetching or when addresses of a specific range has been accessed in referring data, the same address is stored in a plurality of entries of the address information storing unit 2, this resulting in wasteful use of the memory area.
As mentioned above, when the memory accessing frequency of the microprocessor is higher, it is possible to reduce the number of memory elements required for the address information storing unit 2 by constituting the address information storing unit 2 commonly or hierarchically without undue lowering the system efficiency of the cache memory.
As such prior art there is an invention disclosed in Japanese Patent Application Laid-Open No. 2-161546 (1990) applied by the applicant of the present invention in Japan.
The invention of the Japanese Patent Application Laid-Open No. 2-161546 (1990) features straightforwardly the multistage constitution of tag memory dividing it into the common higher bits and the individual lower bits.
Hereinafter, Japanese Patent Application Laid-Open No. 2-161546 (1990) will be explained.
FIG. 4 is a block diagram showing a specific constitution of the cache memory of the invention disclosed in Japanese Patent Application Laid-Open No. 2-161546 (1990).
In this example, different from the prior art shown in FIG. 1, shown is a cache memory of 2-way set associative system with the address having 7 bits and 4 entries.
In FIG. 4, reference numeral 111 represents an access address which is outputted from the microprocessor (not shown). The access address 111 is made up of 4-bit address tag 112 (corresponding to higher 16 bits of the access address 1 in the prior art shown in FIG. 1), 2-bit entry address 113 and 1-bit byte address 114 (these 3 bits corresponding to the lower 8 bits of the access address 1 in the prior art of FIG. 1).
Reference numeral 115 represents a decoder for decoding the entry address 113 of the access address 111 and is corresponding to the address decoder 5 in FIG. 1.
Reference numeral 166 (166a, 166b) represents a first tag memory, and in this cache memory shown in FIG. 4, is composed of 2 bits for storing bits corresponding to the higher 2 bits of the address tag 112 composed of 4 bits of the access address 111 of each data.
Reference numeral 176 (176a, 176b) represents a second tag memory, and in the cache memory shown in FIG. 4, stores the lower 2 bits of the address tag 112 composed of 4 bits of the access address 111 of each data.
In other words, the 16-bit width address information storing unit 2 in the prior art shown in FIG. 1 is divided into the several higher bits and the remaining lower bits, and the several higher bits are taken as the first tag memory 166 (166a, 166b) and the remaining lower bits as the second tag memory 176 (176a, 176b).
Accordingly, in the cache memory shown in FIG. 4, only the data of the access address 111 whose higher 2 bits of the address tag 112 agree with 2 bits stored respectively in the first tag memory 166 (166a, 166b) are held in the data memory 118 (118a, 118b).
Reference numeral 118 (118a, 118b) represents a data memory (corresponding to the data storing unit 3 of the prior art shown in FIG. 1), which stores therein 2-byte data specified by the address composed of 2 bits each of the first tag memory 166 and the second tag memory 176.
Reference numeral 117 (117a, 117b) represents a valid bit, showing whether the memory contents of the data memory 118 is valid or not.
Reference numeral 119 (119a, 119b) represents a comparator (corresponding to the comparator 6 of the prior art of FIG. 1), which is used for judging whether the address tag 112 agrees with the address composed of each 2 bits of the first tag memory 166 and the second tag memory 176 or not.
Reference numeral 120 (120a, 120b) represents a byte selector for selecting the byte data of the data memory 118 according to the contents of the byte address 114.
Reference numeral 121 (121a, 121b) represents a hit signal showing the judging result by the comparator 119.
Subscripts "a" and "b" attached to the aforementioned reference numerals 117 to 121, 166 and 176 indicate corresponding to two ways respectively.
Reference numeral 122 represents a way selector selecting an output of the byte selector 120 by the hit signal 121, and 123 represents a data output which is an output of the way selector 122.
Operation of the cache memory of the invention of Japanese Patent Application Laid-Open No. 2-161546 (1990) shown in FIG. 4 is as follows.
When the access address 111 is given from a data processor (not shown) to the cache memory, contents of the first tag memory 166 and contents of the second tag memory 176 of each way indicated by the entry address 113 are given to the comparator 119 as well as contents of the data memory 118 is given to the byte selector 120. Byte data selected by the byte selector 120 is sent to the way selector 122.
Then, judgment is made whether the contents and the valid bit 117 of the selected second tag memory 176 agrees with the address tag 112 of the access address 111 or not by the comparator 119. When there is an agreeing way, the data of the agreeing way is outputted from the way selector 12 as the data 123. When it is judged as not agreeing, access is made to the external memory (not shown), the data to be required is given to the microprocessor and is stored in the data memory 118 of the cache memory. In addition, the higher 2 bits of the address tag 112 of the access address 111 of the data are required to agree with the contents of the first tag memory 166.
Thus, according to the invention disclosed in Japanese Patent Application Laid-Open No. 2-161546 (1990), the number of memory elements of the tag memory indicating whether the data for accessing by the microprocessor is held or not don't increase in proportion to the holdable data, this resulting in improvement of the hardware efficiency.
In the prior art disclosed in the aforementioned Japanese Patent Application Laid-Open No. 2-161546 (1990), however, no explanation is made to the updating method and timing of the first tag memory shown by the reference numeral 166 (166a, 166b) and the second tag memory shown by 176 (176a, 176b) in FIG. 4.
For example, in the constitution of the cache memory of the direct mapping type shown in FIG. 4, when the tag unit has been commonized to be one and the tag unit is, for example, updated by both the instruction data address and the operand data address at the instruction execution of the microprocessor, there is a high possibility of the address of the instruction data registered once in the cache memory is re-written by the address of the operand data. Hence, the possibility of the cache memory being hit as the next instruction data has been accessed to is lowered, this possibility resulting in failure to operate efficiency.
Thus, in the constitution of the conventional cache memory, it was necessary to have an address data storing unit for storing the memory address in each of the entries for registering data. When the address information storing unit alone is downsized, however, it is likely to result in lowering of the hit ratio and there is a risk of the cache memory not operating efficiently.